package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
*   @description https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
*   @author 曲大人的喵
*   @create 2025/9/5 20:43
*   @since JDK17
*/

public class Solution79 {
    int[][] dp;
    int dfs(char[] s, int l, int r) {
        if (l == r) {
            return 0;
        }
        if (l == r - 1) {
            return s[l] == s[r] ? 0 : 1;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        if (s[l] == s[r]) {
            return dp[l][r] = dfs(s, l + 1, r - 1);
        } else {
            return dp[l][r] = Math.min(dfs(s, l + 1, r), dfs(s, l, r - 1)) + 1;
        }
    }
    public int minInsertions(String s) {
        int n = s.length();
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(s.toCharArray(), 0, n - 1);
    }
}
